0324. 摆动排序 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 排序 + 穿插

1. 📝 题目描述

• leetcode

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

---

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

---

提示：

• 1 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 5000
• 题目数据保证，对于给定的输入 nums，总能产生满足题目要求的结果

进阶：你能用 $O(n)$ 时间复杂度和 / 或原地 $O(1)$ 额外空间来实现吗？

2. 🎯 s.1 - 排序 + 穿插

c

int cmp(const void* a, const void* b) { return *(int*)a - *(int*)b; }

void wiggleSort(int* nums, int numsSize) {
    int* sorted = (int*)malloc(sizeof(int) * numsSize);
    memcpy(sorted, nums, sizeof(int) * numsSize);
    qsort(sorted, numsSize, sizeof(int), cmp);
    int left = (numsSize - 1) / 2, right = numsSize - 1;
    for (int i = 0; i < numsSize; i++) {
        nums[i] = (i % 2 == 0) ? sorted[left--] : sorted[right--];
    }
    free(sorted);
}

js

/**
 * @param {number[]} nums
 * @return {void}
 */
var wiggleSort = function (nums) {
  const sorted = [...nums].sort((a, b) => a - b)
  const n = nums.length
  let left = Math.floor((n - 1) / 2),
    right = n - 1
  for (let i = 0; i < n; i++) {
    nums[i] = i % 2 === 0 ? sorted[left--] : sorted[right--]
  }
}

py

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        sorted_nums = sorted(nums)
        n = len(nums)
        left, right = (n - 1) // 2, n - 1
        for i in range(n):
            if i % 2 == 0:
                nums[i] = sorted_nums[left]
                left -= 1
            else:
                nums[i] = sorted_nums[right]
                right -= 1

• 时间复杂度：$O(n\log n)$，排序
• 空间复杂度：$O(n)$，排序副本

算法思路：

• 排序后将较小的一半从中间往回放偶数位，较大的一半从末尾往回放奇数位
• 逆序穿插可以避免相邻元素相等的问题